package com.example.demo2recursion;

/**
 * 目标：递归解决猴子吃桃问题。
 */
public class RecursionDemo3 {
    public static void main(String[] args) {
        /*
        题目
        # 猴子吃桃子问题:有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个!以后每天猴子都吃其中的一半，
        # 然后再多吃一个。当到第10天时，想再吃时(即还没吃)，发现只有1个桃子了。问题:最初共多少个桃子?

        推导过程：
        f(n + 1) 表示后一天的桃子数量
        f(n) 表示前一天桃子数量
        因为猴子每天都吃其中的一半在多吃一个所有就有了一下的一个等式
        f(n + 1) = f(n) - f(n) / 2 - 1
        最后移项得到
        f(n) = 2f(n + 1) + 2 这就是公式
         */

        // 公式：
        //       f(n + 1) =  f(n) - f(n) / 2 - 1
        // 移项即可
        // 变形： f(n) = 2f(n + 1) + 2

        // 终结点： f(10) = 1

        // 递归的方向: 没有问题的

        System.out.println(f(1));
        System.out.println(f(2));
        System.out.println(f(3));
        System.out.println(f(4));
    }

    public static int f(int n) {
        if (n == 10) {
            return 1;
        } else {
            return 2 * f(n + 1) + 2;
        }
    }
}
